package fina.kmp;

public class KMP {
    public static int kmp(String word,String key){
        char[] str1 = word.toCharArray();
        char[] str2 = key.toCharArray();
        int[] next = getNext(str2);
        int i = 0;
        int j = 0;
        while(i < str1.length && j < str2.length){
            if(str1[i] == str2[j]){
                i++;
                j++;
            }else if(next[j] == -1){
                i++;
            }else{
                j = next[j];
            }
        }
        return j == str2.length ? i - j : -1;
    }
    public static int[] getNext(char[] str2){
        if(str2.length == 1){
            return  new int[]{-1};
        }
        int[] next = new int[str2.length];
        next[0] = -1;
        next[1] = 0;
        int index = 2;
        int cur = 0;
        while(index < next.length){
            if(str2[index - 1] == str2[cur]){
                next[index++] = ++cur;
            }else if(cur != 0){
                cur = next[cur];
            } else {
                next[index++] = 0;
            }
        }
        return next;
    }

    // for test
    public static String getRandomString(int possibilities, int size) {
        char[] ans = new char[(int) (Math.random() * size) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = (char) ((int) (Math.random() * possibilities) + 'a');
        }
        return String.valueOf(ans);
    }

    public static void main(String[] args) {
        int possibilities = 5;
        int strSize = 20;
        int matchSize = 5;
        int testTimes = 5000000;
        System.out.println("test begin");
        for (int i = 0; i < testTimes; i++) {
            String str = getRandomString(possibilities, strSize);
            String match = getRandomString(possibilities, matchSize);
            if (kmp(str, match) != str.indexOf(match)) {
                System.out.println(kmp(str, match));
                System.out.println(str.indexOf(match));
                System.out.println("Oops!");
            }
        }
        System.out.println("test finish");
    }
}
